from typing import List


class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        res = []
        nums.sort()  # 排序后方便排除重复 [勿忘排序！]

        def dfs(set, begin):
            res.append(set[:])
            for i in range(begin, n):
                if i > begin and nums[i-1] == nums[i]: continue  # 加此一行
                set.append(nums[i])
                dfs(set, i+1)
                set.pop()

        dfs(set=[], begin=0)
        return res
